﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0099_MinDistance : IAlgorithm
    {
        // 72. 编辑距离

        // 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

        // 你可以对一个单词进行如下三种操作：
        //   插入一个字符
        //   删除一个字符
        //   替换一个字符

        // 提示：
        //  0 <= word1.length, word2.length <= 500
        //  word1 和 word2 由小写英文字母组成

        public void Test()
        {
            // 算法参数定义
            var word1 = "horse";
            var word2 = "ros";
            // 算法执行与打印
            Console.WriteLine(MinDistance(word1, word2));
        }

        // 算法
        public int MinDistance(string word1, string word2)
        {
            int n = word1.Length;
            int m = word2.Length;
            // 有一个字符串为空串
            if (n * m == 0)
                return n + m;
            // DP 数组
            var dp = new int[n + 1, m + 1];
            // 边界状态初始化
            for (int i = 0; i < n + 1; i++)
                dp[i, 0] = i;
            for (int j = 0; j < m + 1; j++)
                dp[0, j] = j;
            // 计算所有 DP 值
            for (int i = 1; i < n + 1; i++)
                for (int j = 1; j < m + 1; j++)
                {
                    int left = dp[i - 1, j] + 1;
                    int down = dp[i, j - 1] + 1;
                    int left_down = dp[i - 1, j - 1];
                    if (word1[i - 1] != word2[j - 1])
                        left_down += 1;
                    dp[i, j] = Math.Min(left, Math.Min(down, left_down));
                }
            return dp[n, m];
        }
    }
}
